#pragma once
#include <iostream>
#include <vector>
#include <time.h>
#include <thread>
#include <assert.h>
#include <mutex>
#ifdef _WIN32
	#include <Windows.h>
#else
	// ...
#endif
using std::cout;
using std::endl;

static const int MAX_BYTES = 256 * 1024;
static const int NFREELIST = 208;// 桶/链表的个数
static const int NPAGES = 128 + 1;
static const int PAGE_SHIFT = 13;

#ifdef _WIN64
	typedef long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	// linux, mac....
#endif


static void*& NextObj(void* obj)
{
	assert(obj);
	return *((void**)obj);
}

static void* SystemAlloc(size_t nPage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, nPage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);//VirtualAlloc 返回自动对齐到 页 的地址， 即ptr一定为page大小的整数倍
#else
	//
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

//管理小对象的自由链表,(用于ThreadCache::_FreeLists[NFREELIST]
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
	}

	void* Pop()
	{
		assert(_freeList);
		void* ret = _freeList;
		_freeList = NextObj(_freeList);
		return ret;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

	void PushRange(void* start, void* end)// 头插
	{
		NextObj(end) = _freeList;
		_freeList = start;
	}

private:
	size_t _maxSize = 1;
	void* _freeList = nullptr;
};

// 用于计算 size对应的alignSize， index（对其长度，FreeLists数组对应下标）
class SizeClass
{
	// 整体控制在最多10%左右的内碎片浪费
//  申请空间大小			对齐大小		对应数组下标   
// [1,128]					8byte对齐	    freelist[0,16)
// [128+1,1024]				16byte对齐	    freelist[16,72)
// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
// 解释：freelist中第，[0, 16)公差为8， [16, 72)公差为16， [72, 128)公差为72....  每个下标区间内，链表的节点长度是递增的，并不相同。
public:
	// static 使其不用创建SizeClass对象就可以直接使用其成员函数(通过SizeClass::RoundUp(size)即可直接调用）
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else {
			assert(false);
			return -1;
		}
	}

	static inline size_t Index(size_t size)
	{

		assert(size <= MAX_BYTES);

		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };

		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + group_array[0];
		}
		else if (size <= 8 * 1024)
		{
			return _Index(size - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (size <= 64 * 1024)
		{
			return _Index(size - 8*1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size - 64*1024, 13) + group_array[3] + group_array[2] +  group_array[1] + group_array[0];
		}
		else {
			assert(false);
			return -1;
		}
	}

	// 一次thread cache从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t nPage = (num * size >> PAGE_SHIFT);
		nPage = max(1, nPage);
		return nPage;
	}

private:
	// nb的对齐算法
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return  ((bytes + alignNum - 1) & ~(alignNum - 1));
	}
	// nb的求index算法
	static inline size_t _Index(size_t bytes, size_t align_shift/*align_shife = log2(alignNum)*/)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

};

// 管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageId = 0; // 大块内存起始页的页号
	size_t  _n = 0;      // 页的数量

	Span* _next = nullptr;	// 双向链表的结构
	Span* _prev = nullptr;

	size_t _useCount = 0; // 切好小块内存，被分配给thread cache的计数
	void* _freeList = nullptr;  // 切好的小块内存的自由链表
};

// 带头双向循环链表 
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head->_next = _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		pos->_prev = newSpan;
		newSpan->_next = pos;
	}

	void Erase(Span* pos)// 不能delete pos， pos要还给page层
	{
		Span* prev = pos->_prev;
		prev->_next = pos->_next;
		pos->_next->_prev = prev;
		pos->_next = nullptr;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	void PushFront(Span* span)
	{
		Insert(_head->_next, span);
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}


private:
	Span* _head;

public:
	std::mutex _mtx;// 桶锁
};


